#include <stdio.h>
typedef  int ElementType;
/* 希尔排序 - 用Sedgewick增量序列 */
void Shell_Sort(ElementType A[],int N) {
    int Si,D,P,i;
    ElementType Tmp;
    int SedgeWick[] = {929,525,209,109,41,19,5,1,0};
    for(Si = 0;SedgeWick[Si] >= N;Si++); // 5
    for(D = SedgeWick[Si]; D > 0; D = SedgeWick[++Si]) {
        for(P = D;P < N; P++) {
            Tmp = A[P];
            for(i = P; i >= D && A[i -D] > Tmp;i-=D) {
                A[i] = A[i-D];
            }
            A[i] = Tmp;
        }

    }
}
















void Shell_Sort1(ElementType A[],int N) {
    int Si,p,d,i;
    ElementType Tmp;
    /* Sedgewick增量序列 */
    ElementType SedgeWick[] ={260609,146305,64769,36289,
                               16001,8929,3905,2161,929, 505,
                               209, 109, 41, 19, 5, 1, 0};
    for(Si  = 0;SedgeWick[Si] >= N;Si++); /* 找到小于N的第一个数 */
    for(d = SedgeWick[Si];d>0;d=SedgeWick[++Si]) {  /* 开始SedgeWick[Si]个间隔排序 */
        for(p = d;p<N;p++) {
            Tmp = A[p];
            /* A[i-d]大于Tmp时开始插入排序*/
            for(i = p;i >= 0 && A[i - d] > Tmp;i-=d) {
                A[i] = A[i-d];
            }
            A[i] = Tmp;
        }
    }
}


int main() {
    int arr[] = {9,8,3,6,4,7,9,1,2,34,5};
    Shell_Sort1(arr,11);
    for (int i = 0; i < 11; ++i) {
        printf("%d ",arr[i]);
    }

    return 0;
}
